// Demo_Prim.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"

//---------------------------------
//--Thu vien doc file
#include "fstream"
#include "iostream"
using namespace std;
//---------------------------------

#define MAX 100
//---------------------------------
class Canh
{
public:
	int u;
	int U() const { return u; }
	void U(int val) { u = val; }
	int v;
	int V() const { return v; }
	void V(int val) { v = val; }
protected:
	
private:
};
class PrimAlg
{
public:
	//--Ham doc file
	void GetData(const char *filename);
	//--Ham xuat ra man hinh
	void OutScreen();
	//--Ham Prim
	void Run(int v0);
	//--Ham chon dinh
	void ChonDinhV(int v);
	//--Ham tim canh
	int TimCanh(Canh &e, int &trongso);
	//--Ham chon canh
	void ChonCanh(Canh e);
	//--Ham sap xep canh
	void SapXepCanh1(Canh &e);
	void SapXepCanh2();
protected:
	//---------------------------------
	//--Thanh phan Ma tran ke
	//---So dinh cua Ma tran ke
	int nVertex;
	//---Ma tran ke
	int M[MAX][MAX];
	//---------------------------------
	//--Mang X
	int X[MAX];
	int nX;
	//--Mang Y
	int Y[MAX];
	int nY;
	//--Mang Canh
	Canh C[MAX];
	int nC;
	//--Mang Canh da sap xep
	Canh D[MAX];
	int nD;
	//--Trong so
	int trongso;
private:
};
//---------------------------------
void PrimAlg::Run(int v0)
{
	//--X la tap cac dinh cua do thi
	for (int i = 0; i < nVertex; i++)
	{
		X[i] = i;
	}
	nX = nVertex;
	int nT = 0;
	trongso = 0;
	nY = 0;
	nC = 0;
	//--Buoc 1: Chon dinh v0 va khoi tao Y={v0}
	ChonDinhV(v0);
	//--Buoc 2: Trong so nhung canh e noi dinh w voi dinh v0 ta chon canh co trong luong nho nhat
	while(nT < nVertex - 1)
	{
		//--Buoc 3: Y= Y + {w} va T = T + {e}
		//--Buoc 4: Neu T = n - 1 phan tu thi dung, nguoc lai sang buoc 2
		Canh e;
		if (TimCanh(e, trongso) == 1)
		{
			nT = nT + 1;
		}
	}
	SapXepCanh2();
}
//--Ham hoan vi
void Hoanvi(int &a,int &b)
{
	int c;
	c = a;
	a = b;
	b = c;
}
//--Ham sap xep canh
void PrimAlg::SapXepCanh1(Canh &e)
{
	if (e.u > e.v)
	{
		Hoanvi(e.u,e.v);
	}

}
//--Ham Chon canh
void PrimAlg::ChonCanh(Canh e)
{
	int min = -1;
	SapXepCanh1(e);
	C[nC] = e;
	nC = nC + 1;
}
//---------------------------------
void PrimAlg::ChonDinhV(int v)
{
	
	//--Y=Y+{v}
	Y[nY]=v;
	nY++;
	//--X=X\{v}
	//--Tim vi tri muon xoa
	int vitri;
	for(int i = 0; i <nX; i++)
	{
		if(X[i] == v)
		{
			vitri = i;
			break;
		}
	}
	for(int i = vitri; i < nX; i++)
	{
		X[i] = X[i+1];
	}
	nX = nX - 1;
}
//--Ham tim canh
int PrimAlg::TimCanh(Canh &e, int &trongso)
{
	int dinh;
	int x1;
	int y1;
	int min = -1;
	for (int i = 0; i < nX; i ++)
	{
		for (int j = 0; j < nY; j++)
		{
			y1 = Y[j];
			x1 = X[i];
			if (( min == -1 && M[x1][y1] > 0 )|| (( M[x1][y1] > 0 ) && ( M[x1][y1] < min )))
			{
				min = M[x1][y1];
				e.u = x1;
				e.v = y1;
				dinh = x1;
			}
		}
	}
	if(min == -1)
	{
		return 0;
	}
	else
	{
		trongso += min;
		ChonDinhV(dinh);
		ChonCanh(e);
		return 1;
	}
}
//--Ham doc file
void PrimAlg::GetData(const char *filename)
{
	//--Nhap du lieu tu tap tin van ban
	ifstream fin;
	fin.open(filename);
	fin >> nVertex;
	for (int i=0;i<nVertex;++i)
	{	
		for (int j=0;j<nVertex;++j)
		{
			fin >> M[i][j];
		}
	}
}
void PrimAlg::SapXepCanh2()
{
	nD = 0;
	for (int i = 0; i < nC; i++)
	{
		for (int j = 0;j < nC; j++)
		{
			if(C[j].u == i)
			{
				D[nD] = C[j];
				nD = nD + 1;
			}
		}
	}
	for (int i = 0; i < nD; i++)
	{
		for (int j = 0;j < nD; j++)
		{
			if ((D[i].u == i) &&(D[j].u == i) && (D[i].v > D[j].v)) 
			{
				Hoanvi(D[i].u,D[j].u);
				Hoanvi(D[i].v,D[j].v);
			}
		}
	}
}
//---------------------------------
//--Ham xuat ra man hinh
void PrimAlg::OutScreen()
{
	printf("%d\n",trongso);
	for (int i = 0; i < nD-1; i++)
	{	
		printf("(%d,%d);",D[i].u,D[i].v);
	}
	printf("(%d,%d)",D[nD - 1].u,D[nD - 1].v);
}

void main(int argc, _TCHAR* argv[])
{
	PrimAlg P;
	P.GetData("../input.txt");
	P.Run(0);

	P.OutScreen();
}

